package com.zgf.twoTree;

import java.util.*;

public class LinkedBinaryTree  implements BinaryTree{

    private Node root; //根节点

    public LinkedBinaryTree() {

    }

    public LinkedBinaryTree(Node root) {
        this.root = root;
    }

    @Override
    public boolean isEmpty() {
        return  root ==null;
    }

    /**
     * 二叉树的结点数量*/
    @Override
    public int size() {
        System.out.println("二叉树的节点数量为");
        return   this.size(root);
    }
    private int size(Node node) {
        if ( node == null){
            return 0;
        }else {
            //左子树的数量
            int leftNumber  = this.size(node.leftChild);
            //右子树的数量
            int rightNumber = this.size(node.rightChild);
            return leftNumber+rightNumber+1;
        }
    }

    /**
     * 二叉树的高度*/
    @Override
    public int getHeight() {
        System.out.println("二叉树的高度是：");
        return  this.getHeight(root);
    }
    private  int getHeight(Node node) {
        if (node == null){
            return 0;
        }else {
            //左子树的高度
            int leftHight = this.getHeight(node.leftChild);
            // System.out.println("左子树"+leftHight);

            //右子树的高度
            int rightHeight = this.getHeight(node.rightChild);
            //    System.out.println("右子树"+rightHeight);
            return leftHight>rightHeight ? leftHight+1:rightHeight+1;
        }

    }




    /**
     * 查找结点*/
    @Override
    public Node findKey(int value) {
        return this.findKey(value,root);
    }
    private Node findKey(Object value,Node node) {
        //如果根结点为空 则返回 null
        if (node ==null){
            return null;
        }
        //如果   根节点不为空 且  根结点  和 查询的结点相同 则 返回根结点
        else if (node!=null && node.value ==value){
            return node;
        }
        // 查找左子树右子树 递归调用
        else {
            Node node1  =  this.findKey(value,node.leftChild);
            Node node2  =  this.findKey(value,node.rightChild);
            //左子树的结点与查找的值相同 返回左子树
            if (node1 != null && node1.value ==value){
                return node1;
            }
            //右子树的结点与查找的值相同 返回右子树
            else if (node2 != null && node2.value==value){
                return node2;
            }
            //没查到 返回 空
            else {
                return null;
            }
        }
    }


    /**
     * 先序遍历*/
    private void preOrderTraverse(Node root) {
        //先根
        if (root != null){
            System.out.print(root.value+" ");
            //左子树
            this.preOrderTraverse(root.leftChild);
            //右子树
            this.preOrderTraverse(root.rightChild);
        }
    }
    @Override
    public void preOrderTraverse() {
        System.out.println("先序序遍历");
        this.preOrderTraverse(root);
        System.out.println();
    }
    /**
     * 中序遍历*/
    @Override
    public void inOrderTraverse() {
        System.out.println("中序遍历");
        this.inOrderTraverse(root);
        System.out.println();
    }
    private void inOrderTraverse(Node root) {
        if (root != null){
            this.inOrderTraverse(root.leftChild);
            System.out.print(root.value+" ");
            this.inOrderTraverse(root.rightChild);
        }
    }


    /**
     * 后序遍历*/
    @Override
    public void postOrderTraverse() {
        System.out.println("后序遍历");
        this.postOrderTraverse(root);
        System.out.println();
    }
    private void postOrderTraverse(Node root) {
        if (root !=null){
            //左子树
            this.postOrderTraverse(root.leftChild);
            //右子树
            this.postOrderTraverse(root.rightChild);
            //根
            System.out.print(root.value+" ");
        }
    }



    /**
     * 按照层次进行遍历二叉树
     * 未使用递归*/
    @Override
    public void levelOrderByStack() {
        System.out.println("按层次进行遍历");
        if (root == null) return;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (queue.size()!=0){
            int len = queue.size();
            for (int i=0;i<len;i++){
                Node temp = queue.poll();
                System.out.print(temp.value+" ");
                if (temp.leftChild!=null) queue.add(temp.leftChild);
                if (temp.rightChild!=null) queue.add(temp.rightChild);
            }
        }
        System.out.println();
    }
  /** 非递归中序遍历
   * 利用栈来存储数据 并输出  后进先出
   * */
    @Override
    public void NotinOrderTraverse() {
        System.out.println("非递归中序遍历");
        Deque<Node> stack = new LinkedList<Node>();
        if (root==null){
            System.out.println("二叉树为空");
        }else {
        Node current= root;
        while (!stack.isEmpty() || current !=null){
            while (current !=null ){
                stack.push(current);
                current =current.leftChild;
            }
            if (!stack.isEmpty()){
                current= stack.pop();
                System.out.print(current.value+" ");
                current = current.rightChild;

            }
        }
        }
        System.out.println();
    }

    /** 非递归前序遍历*/
    @Override
    public void NotpreOrderTraverse() {
        System.out.println("非递归前序遍历");
        List<Integer> resultList=new ArrayList<>();
        Stack<Node> treeStack=new Stack<>();
        treeStack.push(root);
        while(!treeStack.isEmpty()){
            Node tempNode=treeStack.pop();
            if(tempNode!=null){
                resultList.add((Integer)tempNode.value);//访问根节点
                treeStack.push(tempNode.rightChild); //入栈右孩子
                treeStack.push(tempNode.leftChild);//入栈左孩子
            }
        }
        System.out.println(resultList);
    }
}
